package leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/8 0008.
 */
public class Merge_Intervals {
    public List<Interval> merge(List<Interval> intervals) {

        List<Interval> rst = new LinkedList<Interval>();
        if (intervals == null || intervals.isEmpty()) {
            return rst;
        }
        int maxIdx = Integer.MIN_VALUE, minIdx = Integer.MAX_VALUE;
        for (Interval interval : intervals) {
            if (minIdx > interval.start)
                minIdx = interval.start;
            if (maxIdx < interval.end)
                maxIdx = interval.end;
        }
        int[][] Base = new int[maxIdx - minIdx + 1][2];
        for (Interval interval : intervals) {
            Base[interval.start - minIdx][0] += 1;
            Base[interval.end - minIdx][1] -= 1;
        }
        int base = 0;
        int start = 0, end = 0;
        for (int i = 0; i < Base.length; i++) {
            if (base == 0 && base + Base[i][0] != 0) {
                base += Base[i][0];
                start = i;
            } else {
                base += Base[i][0];

            }
            if (base != 0 && base + Base[i][1] == 0) {
                base += Base[i][1];
                end = i;
                rst.add(new Interval(start + minIdx, end + minIdx));
            } else {
                base += Base[i][1];
            }
        }

        return rst;
    }

    public static void main(String[] args) {
        Merge_Intervals merge_intervals = new Merge_Intervals();
        List<Interval> intervals = new LinkedList<Interval>();
        intervals.add(new Interval(0, 0));

        intervals.add(new Interval(1, 5));
        intervals.add(new Interval(6, 18));
        List<Interval> rst = merge_intervals.merge(intervals);
        for (Interval interval : rst) {
            System.out.println(interval.start + "  " + interval.end);

        }

    }
}
